//
//  ProblemMS1005.swift
//  TestProject
//
//  Created by 武侠 on 2021/5/6.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 面试题 10.05. 稀疏数组搜索
 稀疏数组搜索。有个排好序的字符串数组，其中散布着一些空字符串，编写一种方法，找出给定字符串的位置。

 示例1:
  输入: words = ["at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""], s = "ta"
  输出：-1
  说明: 不存在返回-1。
 
 示例2:
  输入：words = ["at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""], s = "ball"
  输出：4
 提示:

 words的长度在[1, 1000000]之间
 */
@objcMembers class ProblemMS1005: NSObject {
    func solution() {
        print(findString(["at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""], "ta"))
        print(findString(["at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""], "ball"))
    }
    
    /*
     二分法
     1: 让左指针指向左侧第一个非空下标，右指针指向右侧第一个非空下标
     2: 计算mid的位置，如果然后计算mid第一个非空的位置
     */
    func findString(_ words: [String], _ s: String) -> Int {
        var l = 0
        var r = words.count-1
        var mid = 0
        while l <= r {
            while words[l].count == 0 {     // 左边第一个非空
                l += 1
            }
            while words[r].count == 0 {     // 右边第一个非空
                r -= 1
            }
            if l > r {
                return -1
            }
            
            mid = l + (r - l) >> 1
            while words[mid].count == 0 {   // 中间第一个非空
                mid += 1
            }
            
            if words[mid] == s {
                return mid
            } else if words[mid] > s {
                r = mid - 1
            } else {
                l = mid + 1
            }
        }
        return -1
    }
}
